// 组团买票
// 景区里一共有m个项目，景区的第i个项目有如下两个参数：
// game[i] = { Ki, Bi }，Ki、Bi一定是正数
// Ki代表折扣系数，Bi代表票价
// 举个例子 : Ki = 2, Bi = 10
// 如果只有1个人买票，单张门票的价格为 : Bi - Ki * 1 = 8
// 所以这1个人游玩该项目要花8元
// 如果有2个人买票，单张门票的价格为 : Bi - Ki * 2 = 6
// 所以这2个人游玩该项目要花6 * 2 = 12元
// 如果有5个人买票，单张门票的价格为 : Bi - Ki * 5 = 0
// 所以这5个人游玩该项目要花5 * 0 = 0元
// 如果有更多人买票，都认为花0元(因为让项目倒贴钱实在是太操蛋了)
// 于是可以认为，如果有x个人买票，单张门票的价格为 : Bi - Ki * x
// x个人游玩这个项目的总花费是 : max { x * (Bi - Ki * x), 0 }
// 单位一共有n个人，每个人最多可以选1个项目来游玩，也可以不选任何项目
// 所有员工将在明晚提交选择，然后由你去按照上面的规则，统一花钱购票
// 你想知道自己需要准备多少钱，就可以应付所有可能的情况，返回这个最保险的钱数
// 数据量描述 : 
// 1 <= M、N、Ki、Bi <= 10^5
// 来自真实大厂笔试，没有在线测试，对数器验证

#include <bits/stdc++.h>

using namespace std;

int f(int i, int n, int m, vector<vector<int>>& games, vector<int>& cnts)
{
    int ans = 0;
    // 后续没人了
    if(i == n)
    {
        for(int j = 0, k, b, x; j < m; ++j)
        {
            k = games[j][0]; // 折扣系数
            b = games[j][1]; // 门票原价
            x = cnts[j]; // 选择该游戏项目的人生
            ans += max(0, (b - k * x) * x);
        }
    }
    else
    {
        // i 这个人不选择任何的游戏项目
        ans = f(i + 1, n, m, games, cnts); 
        // i 这个人选择 j 这个游戏项目
        for(int j = 0; j < m; ++j)
        {
            ++cnts[j];
            ans = max(ans, f(i + 1, n, m, games, cnts));
            --cnts[j];
        }
    }
    return ans;
}

// 暴力方法
// 为了验证
// 每个人做出所有可能的选择
// 时间复杂度O((m+1)的n次方)
// n : 人数
// m : 游戏项目数
int enough1(int n, vector<vector<int>>& games)
{
    int m = games.size();
    vector<int> cnts(m);
    return f(0, n, m, games, cnts);
}

struct Game
{
    int ki; // 折扣系数
    int bi; // 门票原价
    int people; // 之前的人数

    Game(int k, int b)
    {
        ki = k;
        bi = b;
        people = 0;
    }

    // 如果再来一人，这个项目得到多少钱
    int earn() const
    {
        // bi - (people + 1) * ki : 当前的人，门票原价减少了，当前的门票价格
        // people * ki : 当前人的到来，之前的所有人，门票价格都再减去ki
        return bi - (people + 1) * ki - people * ki;
    }

    // 大根堆采用的是小于号比较
    bool operator<(const Game& other) const
    {
        return earn() < other.earn();
    }
};

// 正式方法
// 时间复杂度O(n * logm)
int enough2(int n, vector<vector<int>>& games)
{
    // 哪个项目，再来一人挣得最多
    // 大根堆
    priority_queue<Game> heap;
    for(auto& g : games) heap.push(Game(g[0], g[1]));
    int ans = 0;
    for(int i = 0; i < n; ++i)
    {
        // 一个个的人，依次送到当前最挣钱的项目里去
        if(heap.top().earn() <= 0) break;
        Game cur = heap.top();
        heap.pop();
        ans += cur.earn();
        ++cur.people;
        heap.push(cur);
    }
    return ans;
}

// 为了验证
vector<vector<int>> randomGames(int m, int v)
{
    vector<vector<int>> ans(m, vector<int>(2));
    for(int i = 0; i < m; ++i)
    {
        ans[i][0] = rand() % v + 1; // 折扣系数
        ans[i][1] = rand() % v + 1; // 门票原价
    }
    return ans;
}

// 为了验证
int main()
{
    srand(time(nullptr));
    int N = 8;
    int M = 8;
    int V = 20;
    int testTimes = 2000;
    cout << "测试开始" << endl;
    for(int i = 1; i <= testTimes; ++i)
    {
        int n = rand() % N + 1;
        int m = rand() % M + 1;
        vector<vector<int>> games = randomGames(m, V);
        int ans1 = enough1(n, games);
        int ans2 = enough2(n, games);
        if(ans1 != ans2) cout << "出错了！" << endl;
        if(i % 100 == 0) cout << "(测试到第" << i << "组)" << endl;
    }
    cout << "测试结束" << endl;

    return 0;
}